Binary Indexed Tree (BIT)
#Data_Structure
Abstract
長さ$ Nの数列$ a = (a_1, \dots, a_N)に対して,
Sum: 与えられた$ i \in \{ 0, \dots, N \}に対し, 数列の和$ \sum_{j = 0}^{i} a_j ~ (a_0 := 0)を返す
Add: 与えられた$ i \in \{ 1, \dots, N \}と$ xに対し, 数列の$ i番目の項を$ a_i \gets a_i + xと更新する
の二つの操作がともに$ O(\log N)timeで行えるデータ構造. Fenwick木ともいう.
Explanation
TODO 書く.
Implementation
BITの構築
Input
数列の長さ N
初期の数列 init を与えることも可能
Output
長さ$ Nの数列を格納したBIT BIT(N)
初期の数列 init が与えられた場合は, init が格納されたBIT
Time complexity
数列 init の長さを$ Nとすると,
数列 init が空のとき$ O(1)time,
そうでないとき, $ O(N)time.
Sum操作
Input
インデックス i
Output
BITに現在格納されている数列の第 i 項目までの和 S
Time complexity
$ O(\log N)time.
Add操作
Input
インデックス i
値 x
Output
なし
BITに格納されている数列の第 i 項目に x が加算される.
Time complexity
$ O(\log N)time.
code:python
class BIT:
def __init__(self, n, init=None):
self.size = n
if init is None:
self.v = 0 * (n + 1) # don't use bit0
else:
self.v = 0 + list(init)
for i in range(1, n):
if i + (i & -i) <= n: self.vi + (i & -i) += self.vi
def sum(self, i):
if i < 0 or i > N: raise IndexError
S = 0
while i > 0:
S += self.vi
i -= i & -i
return S
def add(self, i, x):
if i <= 0 or i > N: raise IndexError
while i <= self.size:
self.vi += x
i += i & -i
Verification
Point Add Range Sum
References
Binary Indexed Tree
Binary Indexed Tree のはなし
フェニック木(Binary Indexed Tree)